#include <stdio.h>
#include <stdlib.h>

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20

typedef int Vertex;     // 结点数据类型
typedef int WeightType; // 权值数据类型
typedef char DataType;  // 顶点存储的信息数据类型

// 边的定义
typedef struct ENode *PtrToENode;
struct ENode
{
    Vertex V1, V2;     // 结点编号
    WeightType weight; // 权重
};
typedef PtrToENode Edge;
// 邻接点的定义
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode
{
    Vertex AdjV;        // 邻接点下标
    WeightType weight;  // 边权重
    PtrToAdjVNode next; // 指向下一个邻接点
};
// 顶点表头结点的定义
typedef struct VNode
{
    PtrToAdjVNode FirstEdge; // 边表头指针
    DataType data;           // 数据
} AdjList[MAX_VERTEX_NUM];

// 图结点的定义
typedef struct GNode *PtrToGNode;
struct GNode
{
    int Nv;
    int Ne;
    AdjList G; // 邻接表
};
typedef PtrToGNode LGraph;

// 创建一个有结点但是没有边的图
LGraph CreateGraph(int VertexNum)
{
    Vertex V; // 遍历用
    LGraph Graph;

    Graph = (LGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    // 初始化邻接表头指针
    for (V = 0; V < Graph->Nv; V++)
        Graph->G[V].FirstEdge = NULL;
}

// 通过插入边来进行图的构建
void Insert(LGraph Graph, Edge E)
{
    PtrToAdjVNode NewNode;
    // 插入边<V1,V2>
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->weight = E->weight;
    // 将V2插入V1的表头
    NewNode->next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;

    // 若是无向图，还需要插入边<V2,V1>
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->weight = E->weight;
    NewNode->next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}
// 创建图
LGraph BuildGraph()
{
    LGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;

    scanf("%d", &Nv);
    Graph = CreateGraph(Nv); // 初始化有Nv结点但没有边的图

    scanf("%d", &(Graph->Nv)); // 边数
    if (Graph->Nv != 0)
    {
        E = (Edge)malloc(sizeof(struct ENode));
        // 按“起点 终点 权重”的顺序读入
        for (i = 0; i < Graph->Ne; i++)
        {
            scanf("%d %d %d", E->V1, E->V2, E->weight);
            Insert(Graph, E);
        }
    }

    // 若顶点有数据的话，就读入数据
    for (V = 0; V < Graph->Nv; V++)
        scanf("%c", &(Graph->G[V].data));
    return Graph;
}
